package pro.softzhang.algo.lc900;

public class LC953_VerifyingAnAlienDictionary {
    public static void main(String[] args) {
        String[] words = {"hello","leetcode"};
        String order = "hlabcdefgijkmnopqrstuvwxyz";
        boolean sorted = new Solution().isAlienSorted(words, order);
        System.out.println(sorted);
    }

    static class Solution {
        public boolean isAlienSorted(String[] words, String order) {
            int[] dict = new int[26];
            for (int i = 0; i < order.length(); i++) {
                dict[order.charAt(i) - 'a'] = i;
            }

            for (int i = 0; i < words.length - 1; i++) {
                if(!validWordSort(words[i], words[i + 1], dict)) {
                    return false;
                }
            }
            return true;
        }

        private boolean validWordSort(String w1, String w2, int[] dict) {
            int i = 0;
            for (; i < w1.length() && i < w2.length(); i++) {
                char ch1 = w1.charAt(i), ch2 = w2.charAt(i);
                if(dict[ch1 - 'a'] > dict[ch2 - 'a']) {
                    return false;
                }

                if(dict[ch1 - 'a'] < dict[ch2 - 'a']) {
                    return true;
                }
            }
            return i == w1.length();
        }
    }
}